package org.aplombh.java.awcing.basic.graph.udg;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
 * <p>
 * 所有边的长度都是 1，点的编号为 1∼n。
 * <p>
 * 请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n 和 m。
 * <p>
 * 接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
 * <p>
 * 输出格式
 * 输出一个整数，表示 1 号点到 n 号点的最短距离。
 * <p>
 * 数据范围
 * 1≤n,m≤105
 * 输入样例：
 * 4 5
 * 1 2
 * 2 3
 * 3 4
 * 1 3
 * 1 4
 * 输出样例：
 * 1
 */
public class TheHierarchyOfPointsInTheGraph_847 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        BreadthFirstSearch bfs = new BreadthFirstSearch(n);
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            bfs.add(a, b);
        }
        System.out.println(bfs.bfs());
    }
}

class BreadthFirstSearch {
    public final static int N = 100010;

    // 存储图
    int[] h = new int[N];
    int[] e = new int[N];
    int[] ne = new int[N];

    //
    int idx, head, tail, n;
    int[] d = new int[N];
    int[] q = new int[N];

    /**
     * 加入从a到b的边,将b加入a点的邻接表中 Add the edge from a to b, add b to the adjacency list at point a
     *
     * @param a a节点 a node
     * @param b b节点 b node
     */
    void add(int a, int b) {
        // 将b存入e中  Store b in e
        e[idx] = b;
        // 将b点的ne指针指向a节点的邻接表的头节点 Set the ne pointer of point B to the head node of the adjacency list of node a
        ne[idx] = h[a];
        // 将a的邻接表的头节点指向b节点 Point the head node of a's adjacency list to b
        h[a] = idx++;
    }

    BreadthFirstSearch(int n) {
        this.n = n;
        init();
    }

    void init() {
        Arrays.fill(h, -1);
        Arrays.fill(d, -1);
        // 从1号出发，到本身距离为0 go from number one, 0 away from itself
        d[1] = 0;
        // 初始化队列，队头为1号元素 Initialize the queue with element 1 as the header
        q[0] = 1;
        // 队列的队头和队尾 The head and tail of the queue
        head = 0;
        tail = 0;
    }

    int bfs() {
        while (head <= tail) {
            // 头节点出列 The head node goes out
            int t = q[head++];
            // 遍历头节点的邻接表 Traverses the adjacency list of the head node
            for (int i = h[t]; i != -1; i = ne[i]) {
                // 挨个遍历所有子节点
                int j = e[i];
                // 如果当前接节点未访问过
                if (d[j] == -1) {
                    // 当前节点的层次为父节点的层次+·
                    d[j] = d[t] + 1;
                    // 将当前节点入栈
                    q[++tail] = j;
                }
            }
        }
        return d[n];
    }
}